Sipser CH2 PROBLEMS'ANSWER 11-15

2.28

2.29

Show is inherently ambiguous.

• 假设存在无歧义CFG识别,考虑如下两个字符集合： ,.均为CFL。
• 应用Pumping Lemma，取,.
• 对于，不难验证pump up的部分必然在中，对同理
• 于是对存在a,b耦合结构，对存在b,c耦合结构。即的parse tree里有只负责生成相应部分的子树。
• 考虑,存在两种不同的parse tree，于是是固有歧义的。

2.30

(a)Consider

(b)Consider

(c)Consider

(d)同(c)

2.31

• 考虑正则语言,假设是CFL，则 是CFL
• 对应用pumping lemma，易得不是CFL
• 矛盾，故不是CFL

2.32

Consider